/**
 * @program: leetcode416
 * @author: JCM
 * @create: 2023-03-23 18:41
 * @description:
 **/
public class Main {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if(len == 1) return false;
        int sum = 0;
        for(int i = 0; i < len; i++) {
            sum += nums[i];
        }
        if(sum %2 != 0) return false;
        int target = sum/2;
        int[] dp = new int[target+1];
        for(int i = 0; i < len;i++) {
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target] == target;
    }
}
